{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cinema Seat Allocation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #bit-manipulation #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #位运算 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumberOfFamilies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安排电影院座位"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/cinema_seats_1.png\" style=\"height: 149px; width: 400px;\"></p>\n",
    "\n",
    "<p>如上图所示，电影院的观影厅中有 <code>n</code>&nbsp;行座位，行编号从 1&nbsp;到 <code>n</code>&nbsp;，且每一行内总共有 10 个座位，列编号从 1 到 10 。</p>\n",
    "\n",
    "<p>给你数组&nbsp;<code>reservedSeats</code>&nbsp;，包含所有已经被预约了的座位。比如说，<code>researvedSeats[i]=[3,8]</code>&nbsp;，它表示第&nbsp;<strong>3</strong>&nbsp;行第&nbsp;<strong>8</strong>&nbsp;个座位被预约了。</p>\n",
    "\n",
    "<p>请你返回&nbsp;<strong>最多能安排多少个 4 人家庭</strong>&nbsp;。4 人家庭要占据&nbsp;<strong>同一行内连续&nbsp;</strong>的 4 个座位。隔着过道的座位（比方说 [3,3] 和 [3,4]）不是连续的座位，但是如果你可以将 4 人家庭拆成过道两边各坐 2 人，这样子是允许的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/03/21/cinema_seats_3.png\" style=\"height: 96px; width: 400px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>上图所示是最优的安排方案，总共可以安排 4 个家庭。蓝色的叉表示被预约的座位，橙色的连续座位表示一个 4 人家庭。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 2, reservedSeats = [[2,1],[1,8],[2,6]]\n",
    "<strong>输出：</strong>2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^9</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;reservedSeats.length &lt;= min(10*n, 10^4)</code></li>\n",
    "\t<li><code>reservedSeats[i].length == 2</code></li>\n",
    "\t<li><code>1&nbsp;&lt;=&nbsp;reservedSeats[i][0] &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;=&nbsp;reservedSeats[i][1] &lt;= 10</code></li>\n",
    "\t<li>所有&nbsp;<code>reservedSeats[i]</code> 都是互不相同的。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cinema-seat-allocation](https://leetcode.cn/problems/cinema-seat-allocation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cinema-seat-allocation](https://leetcode.cn/problems/cinema-seat-allocation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]', '2\\n[[2,1],[1,8],[2,6]]', '4\\n[[4,3],[1,4],[4,6],[1,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort()\n",
    "        res = 2 * n\n",
    "        temp = 0\n",
    "        seat = []\n",
    "        if n > len(reservedSeats):\n",
    "            n = reservedSeats[-1][0]\n",
    "        for i in range(n):\n",
    "            while reservedSeats[temp][0] - 1 == i:\n",
    "                seat.append(reservedSeats[temp][1])\n",
    "                temp += 1\n",
    "                if temp >= len(reservedSeats):\n",
    "                    break\n",
    "            if len(seat) == 1 and (seat[0] != 1 and seat[0] != 10):\n",
    "                res -= 1\n",
    "            if len(seat) >= 2:\n",
    "                if ((2 in seat or 3 in seat) and (6 in seat or 7 in seat)) or ((4 in seat or 5 in seat) and (6 in seat or 7 in seat or 8 in seat or 9 in seat)):\n",
    "                    res -= 2\n",
    "                elif 2 in seat or 3 in seat or 4 in seat or 5 in seat or 6 in seat or 7 in seat or 8 in seat or 9 in seat:\n",
    "                    res -= 1\n",
    "                else:\n",
    "                    res = res\n",
    "            seat = []\n",
    "            if temp >= len(reservedSeats):\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        res=2*n\n",
    "        l=1\n",
    "        f1=f2=f3=0\n",
    "        reservedSeats.sort()\n",
    "       # print(res)\n",
    "        for x,y in reservedSeats:\n",
    "            if x==l:\n",
    "                if 2<=y<=5:\n",
    "                    f1=1\n",
    "                if 6<=y<=9:\n",
    "                    f2=1\n",
    "                if 4<=y<=7:\n",
    "                    f3=1\n",
    "            else:\n",
    "                l=x\n",
    "                print(res,f1,f2,f3)\n",
    "                if f1==f2==f3==1:\n",
    "                    res=res-2\n",
    "                elif f1==f2==f3==0:\n",
    "                    res=res\n",
    "                else:\n",
    "                    res=res-1\n",
    "                \n",
    "                f1=0\n",
    "                f2=0\n",
    "                f3=0\n",
    "                if 2<=y<=5:\n",
    "                    f1=1\n",
    "                if 6<=y<=9:\n",
    "                    f2=1\n",
    "                if 4<=y<=7:\n",
    "                    f3=1\n",
    "                \n",
    "              #  print(res)\n",
    "        \n",
    "        if f1==f2==f3==1:\n",
    "            res=res-2\n",
    "        elif f1==f2==f3==0:\n",
    "            res=res\n",
    "        else:\n",
    "            res=res-1\n",
    "                \n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort(key=lambda x: (x[0],x[1]))\n",
    "        row = 1\n",
    "        reser = []\n",
    "        res = 0\n",
    "        last = reservedSeats[-1]\n",
    "        for i, j in reservedSeats:\n",
    "            while i > row:\n",
    "                y1 = 2 not in reser and 3 not in reser\n",
    "                y2 = 4 not in reser and 5 not in reser\n",
    "                y3 = 6 not in reser and 7 not in reser\n",
    "                y4 = 8 not in reser and 9 not in reser\n",
    "                if y1 and y2 and y3 and y4:\n",
    "                    res += 2\n",
    "                elif (y1 and y2) or (y2 and y3) or (y3 and y4):\n",
    "                    res += 1\n",
    "                row += 1\n",
    "                reser = []\n",
    "            reser.append(j)\n",
    "        y1 = 2 not in reser and 3 not in reser\n",
    "        y2 = 4 not in reser and 5 not in reser\n",
    "        y3 = 6 not in reser and 7 not in reser\n",
    "        y4 = 8 not in reser and 9 not in reser\n",
    "        if y1 and y2 and y3 and y4:\n",
    "            res += 2\n",
    "        elif (y1 and y2) or (y2 and y3) or (y3 and y4):\n",
    "            res += 1\n",
    "        res += (n-row) * 2\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats = sorted(reservedSeats)\n",
    "        res = 0\n",
    "        row = 1\n",
    "        left = True\n",
    "        middle = True\n",
    "        right = True\n",
    "        for r, c in reservedSeats:\n",
    "            # print(r,c)\n",
    "            if r > row:\n",
    "                # print(r, row, left, middle,  right)\n",
    "                row += 1\n",
    "                if left:\n",
    "                    middle = False\n",
    "                    res += 1\n",
    "                if middle:\n",
    "                    res += 1\n",
    "                    right = False\n",
    "                if right:\n",
    "                    res += 1\n",
    "                left = True\n",
    "                middle = True\n",
    "                right = True\n",
    "                if r > row:\n",
    "                    res += 2 * (r - row)\n",
    "                    row = r\n",
    "\n",
    "            if c in [2,3]:\n",
    "                left = False\n",
    "            if c in [4,5]:\n",
    "                middle = False\n",
    "                left = False\n",
    "            if c in [6,7]:\n",
    "                middle = False\n",
    "                right = False\n",
    "            if c in [8,9]:\n",
    "                right = False\n",
    "\n",
    "        # row += 1\n",
    "        # print(r, row, left, middle,  right)\n",
    "        if left:\n",
    "            middle = False\n",
    "            res += 1\n",
    "        if middle:\n",
    "            res += 1\n",
    "            right = False\n",
    "        if right:\n",
    "            res += 1\n",
    "        if n >= row:\n",
    "            res += 2 * (n - row)\n",
    "            row = r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedSeats.sort(key=lambda x: (x[0],x[1]))\n",
    "        row = 1\n",
    "        reser = [0] * 10\n",
    "        res = 0\n",
    "        last = reservedSeats[-1]\n",
    "        for i, j in reservedSeats:\n",
    "            while i > row:\n",
    "                if reser[1:9] == [0]*8:\n",
    "                    res += 2\n",
    "                elif (reser[1:5] == [0]*4) or (reser[3:7] == [0]*4) or (reser[5:9] == [0]*4):\n",
    "                    res += 1\n",
    "                row += 1\n",
    "                reser = [0] * 10\n",
    "            reser[j-1] = 1\n",
    "        if reser[1:9] == [0]*8:\n",
    "            res += 2\n",
    "        elif (reser[1:5] == [0]*4) or (reser[3:7] == [0]*4) or (reser[5:9] == [0]*4):\n",
    "            res += 1\n",
    "        res += (n-row) * 2\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 每一行只有 2345， 4567 ， 6789三种情况可以安排\n",
    "        res = 0\n",
    "        reservedSeats = sorted(reservedSeats,key = lambda x:x[0],reverse = False)\n",
    "        seat = [1] * 10\n",
    "        line = 1\n",
    "        tmp = 0\n",
    "        for r in reservedSeats:\n",
    "            cur_line = r[0]\n",
    "            if line == cur_line:\n",
    "                seat[r[1] - 1] = 0\n",
    "                continue\n",
    "            else:\n",
    "                res += (cur_line-1-line) * 2\n",
    "                \n",
    "                if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "                    tmp += 1\n",
    "                if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "                    tmp += 1\n",
    "                if tmp == 0:\n",
    "                    if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                        tmp += 1\n",
    "                res += tmp\n",
    "\n",
    "                tmp = 0\n",
    "                seat = [1] * 10\n",
    "                line = cur_line\n",
    "                seat[r[1] - 1] = 0\n",
    "        if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "            tmp += 1\n",
    "        if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "            tmp += 1\n",
    "        if tmp == 0:\n",
    "            if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                tmp += 1\n",
    "        res += tmp\n",
    "        res += (n - line) * 2\n",
    "     \n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        idx = 0\n",
    "        num = len(reservedSeats)\n",
    "        reservedSeats.sort(key=lambda x: x[0])\n",
    "        res = 0\n",
    "        for i in range(1, n+1):\n",
    "            seats = [0] * 11\n",
    "            while idx < num and reservedSeats[idx][0] == i:\n",
    "                seats[reservedSeats[idx][1]] = 1\n",
    "                idx += 1\n",
    "            if not sum(seats[2:10]):\n",
    "                res += 2\n",
    "            elif not sum(seats[2:6]) or not sum(seats[4:8]) or not sum(seats[6:10]):\n",
    "                res += 1\n",
    "            if idx == num:\n",
    "                res += (n - i) * 2\n",
    "                break\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 每一行只有 2345， 4567 ， 6789三种情况可以安排\n",
    "        res = 0\n",
    "        reservedSeats = sorted(reservedSeats,key = lambda x:x[0],reverse = False)\n",
    "        seat = [1] * 10\n",
    "        line = 1\n",
    "        tmp = 0\n",
    "        for r in reservedSeats:\n",
    "            cur_line = r[0]\n",
    "            if line == cur_line:\n",
    "                seat[r[1] - 1] = 0\n",
    "                continue\n",
    "            else:\n",
    "                res += (cur_line-1-line) * 2\n",
    "                \n",
    "                if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "                    tmp += 1\n",
    "                if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "                    tmp += 1\n",
    "                if tmp == 0:\n",
    "                    if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                        tmp += 1\n",
    "                res += tmp\n",
    "\n",
    "                tmp = 0\n",
    "                seat = [1] * 10\n",
    "                line = cur_line\n",
    "                seat[r[1] - 1] = 0\n",
    "        if seat[1] and seat[2] and seat[3] and seat[4] :\n",
    "            tmp += 1\n",
    "        if seat[5] and seat[6] and seat[7] and seat[8] :\n",
    "            tmp += 1\n",
    "        if tmp == 0:\n",
    "            if seat[3] and seat[4] and seat[5] and seat[6] :\n",
    "                tmp += 1\n",
    "        res += tmp\n",
    "        res += (n - line) * 2\n",
    "     \n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        '''\n",
    "        maps={}\n",
    "        for i in range(len(reservedSeats)):\n",
    "            if reservedSeats[i][0] not in maps:\n",
    "                maps[reservedSeats[i][0]]=[1]*3\n",
    "                if reservedSeats[i][1] in [2,3,4,5]:\n",
    "                    maps[reservedSeats[i][0]][0]=0\n",
    "                if reservedSeats[i][1] in [4,5,6,7]:\n",
    "                    maps[reservedSeats[i][0]][1]=0\n",
    "                if reservedSeats[i][1] in [6,7,8,9]:\n",
    "                    maps[reservedSeats[i][0]][2]=0\n",
    "            else:\n",
    "                if reservedSeats[i][1] in [2,3,4,5]:\n",
    "                    maps[reservedSeats[i][0]][0]=0\n",
    "                if reservedSeats[i][1] in [4,5,6,7]:\n",
    "                    maps[reservedSeats[i][0]][1]=0\n",
    "                if reservedSeats[i][1] in [6,7,8,9]:\n",
    "                    maps[reservedSeats[i][0]][2]=0\n",
    "        nums=0\n",
    "        #print(maps)\n",
    "        for i in range(1,n+1):\n",
    "            if i not in maps:\n",
    "                nums+=2\n",
    "            else:\n",
    "                if maps[i][0]==1 and maps[i][2]==1:\n",
    "                    nums+=2\n",
    "                elif maps[i][0]==0 and maps[i][1]==0 and maps[i][2]==0:\n",
    "                    continue\n",
    "                else:\n",
    "                    nums+=1\n",
    "        return nums\n",
    "        '''\n",
    "        maps={}\n",
    "        for i in range(len(reservedSeats)):\n",
    "            row=reservedSeats[i][0]\n",
    "            col=reservedSeats[i][1]\n",
    "            if col in [1,10]:\n",
    "                continue\n",
    "            if row not in maps:\n",
    "                maps[row]=[1]*3\n",
    "                if col in [2,3,4,5] and maps[row][0]==1:\n",
    "                    maps[row][0]=0\n",
    "                if col in [4,5,6,7] and maps[row][1]==1:\n",
    "                    maps[row][1]=0\n",
    "                if col in [6,7,8,9] and maps[row][2]==1:\n",
    "                    maps[row][2]=0\n",
    "            else:\n",
    "                if col in [2,3,4,5] and maps[row][0]==1:\n",
    "                    maps[row][0]=0\n",
    "                if col in [4,5,6,7] and maps[row][1]==1:\n",
    "                    maps[row][1]=0\n",
    "                if col in [6,7,8,9] and maps[row][2]==1:\n",
    "                    maps[row][2]=0\n",
    "        nums=2*(n-len(maps))\n",
    "        #print(maps)\n",
    "        for k,v in maps.items():\n",
    "            if 1 in maps[k]:\n",
    "                nums+=1\n",
    "        return nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        l,m,r = 0b11110000,0b11000011,0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for row,seat in reservedSeats:\n",
    "            if 2 <= seat <= 9:\n",
    "                occupied[row] |= (1 << (seat - 2))\n",
    "        \n",
    "        ret = (n - len(occupied)) * 2\n",
    "        for row,mask in occupied.items():\n",
    "            if (mask | l) == l or (mask | m) == m or (mask | r) == r:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left = 0b11110000\n",
    "        right = 0b00001111\n",
    "        mid = 0b11000011\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= 1 << (seat[1] - 2)\n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for k, v in occupied.items():\n",
    "            if (v | left) == left or (v | right) == right or (v | mid) == mid:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        check = [0b00001111, 0b11110000, 0b11000011]\n",
    "        m = defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                m[r] |= 1 << (c - 2)\n",
    "        ans = (n - len(m)) * 2\n",
    "        for val in m.values():\n",
    "            if any(x | val == x for x in check):\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        left = 0b11110000\r\n",
    "        middle = 0b11000011\r\n",
    "        right = 0b00001111\r\n",
    "        x = defaultdict(int)\r\n",
    "        for i in reservedSeats:\r\n",
    "            if 2<= i[1] <=9:\r\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \r\n",
    "        ret = (n - len(x)) * 2\r\n",
    "        for value in x.values():\r\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\r\n",
    "                ret += 1\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "      M = (1 << 11) - 1\n",
    "      L = MID = R = 0\n",
    "      for i in range(2, 6):\n",
    "          L |= 1 << i\n",
    "          MID |= 1 << (i + 2)\n",
    "          R |= 1 << (i + 4)\n",
    "\n",
    "      g = dict()\n",
    "      for i, j in reservedSeats:\n",
    "          g[i] = g.get(i, M) ^ (1 << j)\n",
    "      ans = 2 * n\n",
    "      for v in g.values():\n",
    "          l = v & L == L\n",
    "          r = v & R == R\n",
    "          mid = v & MID == MID\n",
    "          if l and r:\n",
    "              continue\n",
    "          if l or r or mid:\n",
    "              ans -= 1\n",
    "          else:\n",
    "              ans -= 2\n",
    "      return ans\n",
    "              \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, right, mid = 0b00001111, 0b11110000, 0b11000011\n",
    "        m = defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                m[r] |= 1 << (c - 2)\n",
    "        ans = (n - len(m)) * 2\n",
    "        for val in m.values():\n",
    "            if val | left == left or val | right == right or val | mid == mid:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        res = n * 2\n",
    "        reserved_dict = {}\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                if x not in reserved_dict:\n",
    "                    reserved_dict[x] = []\n",
    "                reserved_dict[x].append(y)\n",
    "        \n",
    "        for x in reserved_dict:\n",
    "            res -= 2\n",
    "            reserved_list = sorted(reserved_dict[x])\n",
    "            if len(reserved_list) > 4:\n",
    "                continue\n",
    "            \n",
    "            if len(reserved_list) == 1:\n",
    "                res += 1\n",
    "            elif reserved_list[0] > 5:\n",
    "                res += 1\n",
    "            elif reserved_list[-1] < 6:\n",
    "                res += 1\n",
    "            elif reserved_list[0] < 4 and reserved_list[-1] > 7:\n",
    "                if len(reserved_list) == 2:\n",
    "                    res += 1\n",
    "                elif len(reserved_list) == 3 and (reserved_list[1] < 4 or reserved_list[1] > 7):\n",
    "                    res += 1\n",
    "                elif reserved_list[1] == 3 and reserved_list[2] == 8:\n",
    "                    res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "\n",
    "        families = n * 2\n",
    "\n",
    "        seats = defaultdict(list)\n",
    "\n",
    "        for r, c in reservedSeats:\n",
    "            seats[r].append(c)\n",
    "\n",
    "        for r, cs in seats.items():\n",
    "            left = True\n",
    "            right = True\n",
    "            mid = True\n",
    "            for c in cs:\n",
    "                if c in [2, 3, 4, 5]:\n",
    "                    left = False\n",
    "                if c in [6, 7, 8, 9]:\n",
    "                    right = False\n",
    "                if c in [4, 5, 6, 7]:\n",
    "                    mid = False\n",
    "\n",
    "            if not left:\n",
    "                families -= 1\n",
    "            if not right:\n",
    "                families -= 1\n",
    "            if not left and not right and mid:\n",
    "                families += 1\n",
    "\n",
    "        return families"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        ans -= len(d)\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        mode_left = 0b00001111\n",
    "        mode_mid = 0b11000011\n",
    "        mode_right = 0b11110000\n",
    "\n",
    "        row_state = collections.defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                row_state[r] |= (1 << (c - 2))\n",
    "                \n",
    "        res = (n - len(row_state)) * 2\n",
    "        for r, state in row_state.items():\n",
    "            if (state | mode_left) == mode_left or (state | mode_mid) == mode_mid or (state | mode_right) == mode_right:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left = 0b11110000\n",
    "        middle = 0b11000011\n",
    "        right = 0b00001111\n",
    "        x = defaultdict(int)\n",
    "        for i in reservedSeats:\n",
    "            if 2<= i[1] <=9:\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \n",
    "        ret = (n - len(x)) * 2\n",
    "        for value in x.values():\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\n",
    "                ret += 1\n",
    "        return ret\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        a = {i[0]:7 for i in reservedSeats} #分别设定了3个二进制位分别代表坐下的三种情况。\n",
    "        la = len(a)\n",
    "        # print(a)\n",
    "        cnt = (n - la)*2 #这些行没人坐 每排两个\n",
    "        # print(cnt)\n",
    "        for i in reservedSeats: #对有人坐的行进行标记\n",
    "            if  2 <= i[1] <= 3:\n",
    "                a[i[0]] = a[i[0]] & 6\n",
    "            elif 8 <= i[1] <= 9:\n",
    "                a[i[0]] = a[i[0]] & 5\n",
    "            elif 4 <= i[1] <= 5:\n",
    "                a[i[0]] = a[i[0]] & 2\n",
    "            elif 6 <= i[1] <= 7:\n",
    "                a[i[0]] = a[i[0]] & 1\n",
    "            \n",
    "            # print(i, a[i[0]])\n",
    "        for i in a.items(): #对有人做的计数\n",
    "            if i[1] == 7:\n",
    "                cnt += 2\n",
    "            elif i[1] == 0:\n",
    "                cnt += 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 2)\n",
    "        ret = (n - len(cnt)) * 2\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        for v in cnt.values():\n",
    "            if left | v == left or middle | v == middle or right | v == right:\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        \n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right)== right:\n",
    "                ans += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        a = {i[0]:7 for i in reservedSeats} #分别设定了3个二进制位分别代表坐下的三种情况。\n",
    "        la = len(a)\n",
    "        # print(a)\n",
    "        cnt = (n - la)*2 #这些行没人坐 每排两个\n",
    "        # print(cnt)\n",
    "        for i in reservedSeats: #对有人坐的行进行标记\n",
    "            if  2 <= i[1] <= 3:\n",
    "                a[i[0]] = a[i[0]] & 6\n",
    "            elif 8 <= i[1] <= 9:\n",
    "                a[i[0]] = a[i[0]] & 5\n",
    "            elif 4 <= i[1] <= 5:\n",
    "                a[i[0]] = a[i[0]] & 2\n",
    "            elif 6 <= i[1] <= 7:\n",
    "                a[i[0]] = a[i[0]] & 1\n",
    "            \n",
    "            # print(i, a[i[0]])\n",
    "        for i in a.items(): #对有人做的计数\n",
    "            if i[1] == 7:\n",
    "                cnt += 2\n",
    "            elif i[1] == 0:\n",
    "                cnt += 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 2, 3, 4, 5, 0b11110\n",
    "        # 4, 5, 6, 7, 0b1111000\n",
    "        # 6, 7, 8, 9, 0b111100000\n",
    "        # reserved 2, 3, 8, 0b10000110\n",
    "        left, middle, right = 0b11110, 0b1111000, 0b111100000\n",
    "        l = len(reservedSeats)\n",
    "        i = 1\n",
    "        j = 0\n",
    "        row_reserved = {}\n",
    "        for r, c in reservedSeats:\n",
    "            # process each reserved seat into dict showing reserved status (int) for the row\n",
    "            row_reserved[r] = row_reserved.get(r, 0) + (1 << (c - 1))\n",
    "        res = 2 * (n - len(row_reserved))   # start with non reserved rows\n",
    "\n",
    "        for row, reserved in row_reserved.items():\n",
    "            if left & reserved == 0 and right & reserved == 0:\n",
    "                res += 2\n",
    "            elif middle & reserved == 0 or left & reserved == 0 or right & reserved == 0:\n",
    "                res += 1\n",
    "\n",
    "        # reservedSeats.sort()  # sort not necessary after using dict, TC: O(nlog(n)) to O(n)\n",
    "        # while i <= n:\n",
    "            # reserved = 0\n",
    "            # while j < l and reservedSeats[j][0] == i:\n",
    "            #     reserved += 1 << (reservedSeats[j][1] - 1)\n",
    "            #     j += 1\n",
    "\n",
    "            # if reserved == 0 or (left & reserved == 0 and right & reserved == 0):\n",
    "            #     res += 2\n",
    "            # elif middle & reserved == 0 or left & reserved == 0 or right & reserved == 0:\n",
    "            #     res += 1\n",
    "\n",
    "            # # i += 1\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        ret = 0\n",
    "        for v in cnt.values():\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret + (n - len(cnt)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        bit_mapping = defaultdict(int)\n",
    "        left = 0b00001111\n",
    "        right = 0b11110000\n",
    "        mid = 0b11000011\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1]  <= 9:\n",
    "                bit_mapping[seat[0]] |= (1 << (seat[1] - 2))\n",
    "        result = (n - len(bit_mapping)) * 2\n",
    "        for row, bit in bit_mapping.items():\n",
    "            if (bit | left) == left or (bit | right) == right or (bit | mid) == mid:\n",
    "                result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "        for seat in reservedSeats:\n",
    "            if 2 <= seat[1] <= 9:\n",
    "                occupied[seat[0]] |= (1 << (seat[1] - 2))\n",
    "\n",
    "        ans = (n - len(occupied)) * 2\n",
    "        for row, bitmask in occupied.items():\n",
    "            if (bitmask | left) == left or (bitmask | middle) == middle or (bitmask | right) == right:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 2\n",
    "            elif l or m or r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxNumberOfFamilies(self, n, res):\n",
    "        left = set()\n",
    "        right = set()\n",
    "        mid = set()\n",
    "        count = 0\n",
    "        min_, max_ = n, 0\n",
    "        for r, c in res:\n",
    "            min_ = min(r, min_)\n",
    "            max_ = max(r, max_)\n",
    "            if r in left and r in right and r in mid:\n",
    "                continue\n",
    "            if (c < 6) and (c > 1): left.add(r)\n",
    "            if (c < 10) and (c > 5): right.add(r)\n",
    "            if (c < 8) and (c > 3): mid.add(r)\n",
    "        for i in range(min_, max_+1):\n",
    "            if i not in left and i not in right:\n",
    "                count += 2\n",
    "            elif i not in mid:\n",
    "                count += 1\n",
    "            elif i not in left or i not in right:\n",
    "                count += 1\n",
    "        count += 2*(min_-1)\n",
    "        count += 2*(n-max_)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for x, y in reservedSeats:\n",
    "            insort_left(d[x], y)\n",
    "        ans = (n - len(d)) * 2\n",
    "        for l in d.values():\n",
    "            l.insert(0, 0)\n",
    "            l.append(11)\n",
    "            for i in range(1, len(l)):\n",
    "                if l[i - 1] < 2 and l[i] > 9:\n",
    "                    ans += 2\n",
    "                elif l[i - 1] < 2 and l[i] > 5 or l[i - 1] < 4 and l[i] > 7 or l[i - 1] < 6 and l[i] > 9:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 使用8个二进制位来表示一排座位的预约情况。\n",
    "        # 9 8 7 6 5 4 3 2\n",
    "        left, middle, right = 0b11110000, 0b11000011, 0b00001111\n",
    "        occupied = collections.defaultdict(int)\n",
    "\n",
    "        for seat in reservedSeats:\n",
    "            if 2<=seat[1]<=9:\n",
    "                occupied[seat[0]] = occupied[seat[0]] | (1<<(seat[1]-2))\n",
    "\n",
    "        res = (n-len(occupied)) * 2\n",
    "        for row,bitmask in occupied.items():\n",
    "            if (bitmask | left)==left or (bitmask | middle)==middle or (bitmask | right)==right:\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        y = {}\n",
    "        for i, j in reservedSeats:\n",
    "            if not i in y.keys():\n",
    "                y[i] = [1,1,1]\n",
    "            if 1 < j < 6:\n",
    "                y[i][0] = 0\n",
    "            if 3 < j < 8:\n",
    "                y[i][1] = 0\n",
    "            if 5 < j < 10:\n",
    "                y[i][2] = 0\n",
    "        ans = 2 * n\n",
    "        for a, b in y.items():\n",
    "            if (sum(b) == 2 and b[1] == 1) or sum(b) == 1:\n",
    "                ans -= 1\n",
    "            elif sum(b) == 0:\n",
    "                ans -= 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "cnt = [2, 1, 1, 1, 1, 0, 0, 0, 1, 1,0,0,1,0,0,0]\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        rsv = defaultdict(int)\n",
    "        for row, col in reservedSeats:\n",
    "            if 2<=col<=3 and not (rsv[row-1] >> 3) & 1:\n",
    "                rsv[row-1] += 8\n",
    "            elif 4<=col<=5 and not (rsv[row-1] >> 2) & 1:\n",
    "                rsv[row-1] += 4\n",
    "            elif 6<=col<=7 and not (rsv[row-1] >> 1) & 1:\n",
    "                rsv[row-1] += 2\n",
    "            elif 8<=col<=9 and not (rsv[row-1] & 1):\n",
    "                rsv[row-1] += 1\n",
    "        ans = n*2\n",
    "        for r in rsv.values():\n",
    "            ans += cnt[r]-2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 首先按行，将reservedSeats分组。\n",
    "        # 2345,4567，6789 \n",
    "        rec = defaultdict(list)\n",
    "        for r,c in reservedSeats:\n",
    "            rec[r].append(c)\n",
    "        total = 0\n",
    "        for r,clist in rec.items():\n",
    "            f1,f2,f3 = True, True, True\n",
    "            for c in clist:\n",
    "                if c in [2,3,4,5]: f1 = False\n",
    "                if c in [4,5,6,7]: f2 = False\n",
    "                if c in [6,7,8,9]: f3 = False\n",
    "            if f1 and f3:\n",
    "                total += 2\n",
    "            elif f1 or f2 or f3:\n",
    "                total += 1\n",
    "            pass\n",
    "        total += 2*(n - len(rec))\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        \n",
    "\n",
    "        tplan = 0   \n",
    "        rowrsi = {}\n",
    "        for seat in reservedSeats:\n",
    "            if seat[0] not in rowrsi:\n",
    "                rowrsi[seat[0]] = [] \n",
    "                rowrsi[seat[0]].append(seat[1])\n",
    "            else:\n",
    "                rowrsi[seat[0]].append(seat[1])\n",
    "        for rowrsii in rowrsi:\n",
    "            tplan += self.rowplan(rowrsi[rowrsii]) \n",
    "        return tplan + (n - len(rowrsi))*2\n",
    "\n",
    "    def rowplan(self, rowrs):\n",
    "        if sum([i not in rowrs for i in range(2,10)]) ==8:\n",
    "            return 2\n",
    "        if sum([i not in rowrs for i in range(4,8)]) == 4:\n",
    "            return 1\n",
    "        if sum([i not in rowrs for i in range(2,6)]) ==4 or sum([i not in rowrs for i in range(6,10)])==4:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        mode_left = 0b00001111\n",
    "        mode_mid = 0b11000011\n",
    "        mode_right = 0b11110000\n",
    "\n",
    "        row_state = collections.defaultdict(int)\n",
    "        for r, c in reservedSeats:\n",
    "            if 2 <= c <= 9:\n",
    "                row_state[r] |= (1 << (c - 2))\n",
    "                \n",
    "        res = (n - len(row_state)) * 2\n",
    "        for r, state in row_state.items():\n",
    "            if (state | mode_left) == mode_left or (state | mode_mid) == mode_mid or (state | mode_right) == mode_right:\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedList = defaultdict(list)\n",
    "        for c, r in reservedSeats:\n",
    "            reservedList[c].append(r - 1)\n",
    "        mask1, mask2, mask3, mask4 = 0b0111111110, 0b111100000, 0b1111000, 0b11110\n",
    "        ret = 0\n",
    "        for j in reservedList.keys():\n",
    "            current = 0\n",
    "            for i in range(10):\n",
    "                current = (current << 1) + (i in reservedList[j])\n",
    "            ret += (current & mask1 == 0) + ((current & mask2 == 0) | (current & mask3 == 0) | (current & mask4 == 0))\n",
    "            # print(ret, acc)\n",
    "        return ret + (n - len(reservedList)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        seat = defaultdict(int)\n",
    "        for a, b in reservedSeats:\n",
    "            seat[a] |= 1 << b\n",
    "\n",
    "        ans = (n - len(seat)) * 2\n",
    "        two = sum(1 << x for x in range(2, 10))\n",
    "        left = sum(1 << x for x in range(2, 6))\n",
    "        mid = sum(1 << x for x in range(4, 8))\n",
    "        right = sum(1 << x for x in range(6, 10))\n",
    "\n",
    "        for i in seat:\n",
    "            if not two & seat[i]:\n",
    "                ans += 2\n",
    "            else:\n",
    "                for one in [left, mid, right]:\n",
    "                    if not one & seat[i]:\n",
    "                        ans += 1\n",
    "                        break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "L = 0b0111100000\n",
    "M = 0b0001111000\n",
    "R = 0b0000011110\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            if 1 < j < 10:\n",
    "                d[i] += 1 << j - 1\n",
    "        ans -= len(d)\n",
    "        for v in d.values():\n",
    "            if L & v and M & v and R & v:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ans = n * 2\n",
    "        d = defaultdict(list)\n",
    "        for (i,j) in reservedSeats:\n",
    "            d[i].append(j)\n",
    "        for i in d:\n",
    "            arr = d[i]\n",
    "            left,right,mid = 0,0,1\n",
    "            for j in arr:\n",
    "                if 1< j < 6:\n",
    "                    left = -1\n",
    "                if 3< j < 8:\n",
    "                    mid = 0\n",
    "                if 5 < j < 10:\n",
    "                    right = -1\n",
    "            if left and right:\n",
    "                ans -= 2 - mid\n",
    "            else:\n",
    "                ans += left + right\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        que = defaultdict(list)\n",
    "        for a, b in reservedSeats:\n",
    "            que[a].append(b)\n",
    "        base = (n - len(que)) * 2\n",
    "        for k, v in que.items():\n",
    "            tmp = [0] * 11\n",
    "            for vv in v:\n",
    "                tmp[vv] = 1\n",
    "            acc = list(accumulate(tmp, initial=0))\n",
    "            if acc[10] - acc[2] == 0:\n",
    "                base += 2\n",
    "            elif acc[6] - acc[2] == 0:\n",
    "                base += 1\n",
    "            elif acc[10] - acc[6] == 0:\n",
    "                base += 1\n",
    "            elif acc[8] - acc[4] == 0:\n",
    "                base += 1\n",
    "        return base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        left = 0b11110000\r\n",
    "        middle = 0b11000011\r\n",
    "        right = 0b00001111\r\n",
    "        x = defaultdict(int)\r\n",
    "        for i in reservedSeats:\r\n",
    "            if 2<= i[1] <=9:\r\n",
    "                x[i[0]] |= (1 << (9 - i[1])) # x: {1:0b11000000, 2: 0b00011110, ....} \r\n",
    "        ret = (n - len(x)) * 2\r\n",
    "        for value in x.values():\r\n",
    "            if (value | left) == left or (value | middle) == middle or (value | right) == right:\r\n",
    "                ret += 1\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        ret = (n - len(cnt)) * 2\n",
    "        for v in cnt.values():\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "_FAM_1 = int(\"11110\", 2)\n",
    "_FAM_2 = int(\"1111000\", 2)\n",
    "_FAM_3 = int(\"111100000\", 2)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reserved_seats: List[List[int]]) -> int:\n",
    "        def check_fam_num(row: int) -> int:\n",
    "\n",
    "            l = row & _FAM_1 == 0\n",
    "            r = row & _FAM_3 == 0\n",
    "\n",
    "            if l or r:\n",
    "                return int(l) + int(r)\n",
    "            \n",
    "            return int(row & _FAM_2 == 0)\n",
    "        res = defaultdict(int)\n",
    "        for r, c in reserved_seats:\n",
    "            res[r] |= 1 << c - 1\n",
    "        return (n - len(res)) * 2 + sum(check_fam_num(row) for _, row in res.items())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        reservedList = defaultdict(list)\n",
    "        for c, r in reservedSeats:\n",
    "            reservedList[c].append(r)\n",
    "        ret = 0\n",
    "        for j in reservedList.keys():\n",
    "            current = [0] * 10\n",
    "            for i in reservedList[j]:\n",
    "                current[i - 1] = 1\n",
    "            acc = list(accumulate(current))\n",
    "            ret += (acc[8] - acc[0] == 0) + ((acc[4] - acc[0] == 0) | (acc[6] - acc[2] == 0) | (acc[8] - acc[4] == 0))\n",
    "            # print(ret, acc)\n",
    "        return ret + (n - len(reservedList)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 一开始可以坐这么多人\n",
    "        ans = n * 2\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        # 1表示那个位置有人\n",
    "        for i, j in reservedSeats:\n",
    "            d[i] += 1 << j - 1\n",
    "        for v in d.values():\n",
    "            # 是否不能坐了\n",
    "            l = 0b0111100000 & v\n",
    "            m = 0b0001111000 & v\n",
    "            r = 0b0000011110 & v\n",
    "            if l and m and r:\n",
    "                ans -= 2\n",
    "            elif l or m or r:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        # 首先按行，将reservedSeats分组。\n",
    "        # 2345,4567，6789\n",
    "        # 遍历reverse，根据三个区间是否被占，计算reverse中能放下的家庭数\n",
    "        # 其余没有被占的行，每行都可以放2个家庭\n",
    "        rec = defaultdict(list)\n",
    "        for r,c in reservedSeats:\n",
    "            rec[r].append(c)\n",
    "        total = 0\n",
    "        for r,clist in rec.items():\n",
    "            f1,f2,f3 = True, True, True\n",
    "            for c in clist:\n",
    "                if c in [2,3,4,5]: f1 = False\n",
    "                if c in [4,5,6,7]: f2 = False\n",
    "                if c in [6,7,8,9]: f3 = False\n",
    "            if f1 and f3:\n",
    "                total += 2\n",
    "            elif f1 or f2 or f3:\n",
    "                total += 1\n",
    "            pass\n",
    "        total += 2*(n - len(rec))\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        occ = defaultdict(list)\n",
    "        for line, seat in reservedSeats:\n",
    "            occ[line].append(seat)\n",
    "        ans = 0\n",
    "        for line in occ:\n",
    "            n -= 1\n",
    "            seats_occupied = [False] * 11\n",
    "            for seat in occ[line]:\n",
    "                seats_occupied[seat] = True\n",
    "            if sum(seats_occupied[2: 10]) == 0:\n",
    "                ans += 2\n",
    "            elif sum(seats_occupied[2: 6]) == 0:\n",
    "                ans += 1\n",
    "            elif sum(seats_occupied[6: 10]) == 0:\n",
    "                ans += 1\n",
    "            elif sum(seats_occupied[4: 8]) == 0:\n",
    "                ans += 1\n",
    "        ans += (n * 2)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        seats = {}\n",
    "        result = 0\n",
    "        for a, b in reservedSeats:\n",
    "            if a-1 not in seats:\n",
    "                seats[a-1] = [0] *10\n",
    "            seats[a-1][b-1] = 1\n",
    "        for row in seats.values():\n",
    "            if not any(row[1:9]):\n",
    "                result += 2\n",
    "            elif not any(row[1:5]) or not any(row[5:9]) or not any(row[3:7]):\n",
    "                result += 1\n",
    "        result += 2*(n-len(seats))\n",
    "        return result \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        rowrsi = defaultdict(list)\n",
    "        for seat in reservedSeats:\n",
    "            rowrsi[seat[0]].append(seat[1])\n",
    "        \n",
    "        tplan = 0\n",
    "        for row in rowrsi.values():\n",
    "            tplan += self.rowplan(row)\n",
    "        \n",
    "        empty_rows = n - len(rowrsi)\n",
    "        return tplan + empty_rows * 2\n",
    "    \n",
    "    def rowplan(self, rowrs):\n",
    "        occupied = set(rowrs)\n",
    "        \n",
    "        if all(i not in occupied for i in range(2, 10)):\n",
    "            return 2\n",
    "        if all(i not in occupied for i in range(4, 8)):\n",
    "            return 1\n",
    "        if all(i not in occupied for i in range(2, 6)) or all(i not in occupied for i in range(6, 10)):\n",
    "            return 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        visited = [[0] * 10 for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            visited[x-1][y-1] = 1\n",
    "        pre = list(list(accumulate(v, initial=0)) for v in visited)\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            if pre[i][9] - pre[i][1] == 0:\n",
    "                ret += 2\n",
    "            elif pre[i][7] - pre[i][3] == 0 or pre[i][5] - pre[i][1] == 0 or pre[i][9] - pre[i][5] == 0:\n",
    "                ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        ret = [[1, 1] for _ in range(n)]\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 or y != 10:\n",
    "                if y < 6 and ret[x-1][0]:\n",
    "                    ret[x-1][0] -= 1\n",
    "                if y < 10 and ret[x-1][1]:\n",
    "                    ret[x-1][1] -= 1\n",
    "        return sum(sum(x) for x in ret)\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        cnt = defaultdict(int)\n",
    "        for x, y in reservedSeats:\n",
    "            if y != 1 and y != 10:\n",
    "                cnt[x] |= 1 << (y - 1)\n",
    "        print(cnt)\n",
    "        ret = 0\n",
    "        for v in cnt.values():\n",
    "            print(bin(v))\n",
    "            for i in (1, 3, 5):\n",
    "                if all(v >> j & 1 == 0 for j in range(i, i + 4)):\n",
    "                    ret += 1\n",
    "                    break\n",
    "        return ret + (n - len(cnt)) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "        res=n*2\n",
    "        dit = collections.defaultdict(lambda:[0 for i in range(11)])\n",
    "        for i in reservedSeats:\n",
    "            dit[i[0]][i[1]]=1\n",
    "        for i in dit:\n",
    "            chair=dit[i]\n",
    "            if chair[2:6]!=[0,0,0,0] or chair[6:10]!=[0,0,0,0]:\n",
    "                res-= 2\n",
    "                if chair[2:6]==[0,0,0,0] or chair[6:10]==[0,0,0,0] or chair[4:8]==[0,0,0,0]:\n",
    "                    res+=1  \n",
    "     \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        row2cols = defaultdict(set)\n",
    "        for row, col in reservedSeats:\n",
    "            if col != 1 and col != 10:\n",
    "                row2cols[row].add(col)\n",
    "\n",
    "        res = (n - len(row2cols)) * 2\n",
    "\n",
    "        for cols in row2cols.values():\n",
    "            # {2, 3, 4, 5} {4, 5, 6, 7}, {6, 7, 8, 9}\n",
    "            \n",
    "            if (all(col not in cols for col in {2, 3, 4, 5}) or \n",
    "                all(col not in cols for col in {4, 5, 6, 7}) or \n",
    "                all(col not in cols for col in {6, 7, 8, 9})):\n",
    "                res += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\r\n",
    "        rsv = defaultdict(set)\r\n",
    "\r\n",
    "        for x, y in reservedSeats:\r\n",
    "            if 1 < y < 10:\r\n",
    "                rsv[x].add(y)\r\n",
    "\r\n",
    "        ret = (n - len(rsv)) * 2\r\n",
    "\r\n",
    "        for i in rsv:\r\n",
    "            if 2 not in rsv[i] and 3 not in rsv[i] and 4 not in rsv[i] and 5 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            elif 4 not in rsv[i] and 5 not in rsv[i] and 6 not in rsv[i] and 7 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            elif 6 not in rsv[i] and 7 not in rsv[i] and 8 not in rsv[i] and 9 not in rsv[i]:\r\n",
    "                ret += 1\r\n",
    "            # print(i, ret)\r\n",
    "        return ret\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:\n",
    "\n",
    "        row2cols = defaultdict(set)\n",
    "        for row, col in reservedSeats:\n",
    "            row2cols[row].add(col)\n",
    "\n",
    "        res = (n - len(row2cols)) * 2\n",
    "\n",
    "        for cols in row2cols.values():\n",
    "            # {2, 3, 4, 5} {4, 5, 6, 7}, {6, 7, 8, 9}\n",
    "            \n",
    "            if all(col not in cols for col in {2, 3, 4, 5, 6, 7, 8, 9}):\n",
    "                res += 2\n",
    "            elif (all(col not in cols for col in {2, 3, 4, 5}) or \n",
    "                  all(col not in cols for col in {4, 5, 6, 7}) or \n",
    "                  all(col not in cols for col in {6, 7, 8, 9})):\n",
    "                  res += 1\n",
    "\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
